`
https://leetcode.cn/problems/delete-operation-for-two-strings/
`

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function (word1, word2) {
  // 要使 word1 和 word2 相同
  // 那么删到最后的结果就是 word1 和 word2 的最长公共子序列
  // 直接复用 https://leetcode.cn/problems/longest-common-subsequence/ 的代码即可
  const m = word1.length, n = word2.length
  const lcs = longestCommonSubsequence(word1, word2)
  return m - lcs + n - lcs
};

/**
* @param {string} text1
* @param {string} text2
* @return {number}
*/
var longestCommonSubsequence = function (text1, text2) {
  const m = text1.length, n = text2.length
  const memo = Array.from({ length: m }, () => new Array(n).fill(-1))
  function dp(i, j) {
    if (i === m || j === n) {
      return 0
    }
    if (memo[i][j] !== -1) {
      return memo[i][j]
    }
    if (text1[i] === text2[j]) {
      memo[i][j] = dp(i + 1, j + 1) + 1
    } else {
      memo[i][j] = Math.max(
        dp(i + 1, j),
        dp(i, j + 1)
      )
    }
    return memo[i][j]
  }
  return dp(0, 0)
};